package 中等.贪心思想;

import java.util.HashSet;
import java.util.Set;

/**
 * 在一个由 m 个用户组成的社交网络里，我们获取到一些用户之间的好友关系。
 * 两个用户之间可以相互沟通的条件是他们都掌握同一门语言。
 * 给你一个整数 n ，数组 languages 和数组 friendships ，它们的含义如下：
 * 总共有 n 种语言，编号从 1 到 n 。
 * languages[i] 是第 i 位用户掌握的语言集合。
 * friendships[i] = [u​​​​​​i​​​, v​​​​​​i] 表示 u​​​​​​​​​​​i​​​​​ 和 vi 为好友关系。
 * 你可以选择 一门 语言并教会一些用户，使得所有好友之间都可以相互沟通。请返回你 最少 需要教会多少名用户。
 * 请注意，好友关系没有传递性，也就是说如果 x 和 y 是好友，且 y 和 z 是好友， x 和 z 不一定是好友。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/minimum-number-of-people-to-teach
 */
public class 需要教语言的最少人数_1733 {

    public static void main(String[] args) {

        // 示例 2：
        //输入：n = 3, languages = [[2],[1,3],[1,2],[3]], friendships = [[1,4],[1,2],[3,4],[2,3]]
        //输出：2
        //解释：教用户 1 和用户 3 第三门语言，需要教 2 名用户。

        System.out.println(minimumTeachings(3, new int[][]{{2}, {1, 3}, {1, 2}, {3}},
                new int[][]{{1, 4}, {1, 2}, {3, 4}, {2, 3}}));

    }

    /**
     * 重点：只能选择一门语言教学！！！
     * 统计和好友有沟通障碍的人，并统计他们中最流行的语言
     * 这些人中，没有掌握最流行语言的人数就是答案
     */
    public static int minimumTeachings(int n, int[][] languages, int[][] friendships) {
        // key 为某门语言，value 为掌握该语言的用户集合
        Set<Integer>[] langMapUsers = new Set[n + 1];
        // 有沟通障碍的人
        Set<Integer> needUserSet = new HashSet<>();
        int maxPopular = 0;
        for (int[] friendship : friendships) {
            // 排除能够沟通的好友关系
            boolean flag = false;
            for (int l1 : languages[friendship[0] - 1]) {
                for (int l2 : languages[friendship[1] - 1]) {
                    if (l1 == l2) {
                        flag = true;
                        break;
                    }
                }
            }
            if (flag) continue;

            for (int l1 : languages[friendship[0] - 1]) {
                Set<Integer> set = langMapUsers[l1];
                if (set == null) {
                    set = new HashSet<>();
                    langMapUsers[l1] = set;
                }
                set.add(friendship[0]);
                maxPopular = Math.max(maxPopular, set.size());
            }
            for (int l2 : languages[friendship[1] - 1]) {
                Set<Integer> set = langMapUsers[l2];
                if (set == null) {
                    set = new HashSet<>();
                    langMapUsers[l2] = set;
                }
                set.add(friendship[1]);
                maxPopular = Math.max(maxPopular, set.size());
            }

            needUserSet.add(friendship[0]);
            needUserSet.add(friendship[1]);
        }

        return needUserSet.size() - maxPopular;
    }

}
